package com.LeeCode;

/**
 * 有界数组中指定下标处的最大值
 */

public class Code1802 {
    public static void main(String[] args) {
        System.out.println(new Code1802().maxValue(6, 2, 931384943));
    }

    public int maxValue(int n, int index, int maxSum) {
        int left = 1, right = maxSum - n + 2;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(n, index, maxSum, mid))
                left = mid;
            else
                right = mid;
        }
        return left;
    }

    private boolean check(int n, int index, int maxSum, int num) {
        int left = index, right = n - index - 1;
        int left1 = Math.max(left - num + 1, 0), left2 = Math.min(left, num - 1);
        int right1 = Math.max(right - num + 1, 0), right2 = Math.min(right, num - 1);

        long sum = left1 + right1 + num +
                ((long) 2 * num - 1 - left2) * left2 / 2 + ((long) 2 * num - 1 - right2) * right2 / 2;
        return sum <= maxSum;
    }
}
